'''
Created on Feb 27, 2012

@author: lino possamai - www.possamai.it/lino
@license: GPLv3
'''
import random, sys, time
from random import shuffle

def sel_group_in_probability(lista_prob):
    ''' input: dictionary like {1:set([tuple of nodes]),2:set([tuple of nodes])...} '''
    
    s=0
    lista_cum=[0]
    for k in sorted(lista_prob.keys()):
        s+=(k*len(lista_prob[k]))
        lista_cum.append(s)         #non si prevede che una lista_prob sia vuota
    
    r= random.random()              #generates random fp numbers in [0,1)
    r*=float(s)
     
    i=0
    for j in lista_cum[1:]:
        if i<= r and r<j:
            #print sorted(lista_prob.keys())
            #print lista_cum, i,r,j,lista_cum.index(j), sorted(lista_prob.keys())[lista_cum.index(j)-1] 
            return sorted(lista_prob.keys())[lista_cum.index(j)-1]
        i=j
    print "error in sel_group_in_probability"
    sys.exit()

def select_edge(index, lista_prob_archi, tecnica, graph, g_complete = None):
    
    #index identifies a set of edges (descrittore)
    
    #usiamo il comando pop perche' gli insiemi sono stati shuffled.
    e=lista_prob_archi[index].pop()
    
    #vecchia implementazione con liste
    #e=random.sample(lista_prob_archi[index],1)[0]           #select an edge randomly from a set        
    #lista_prob_archi[index].remove(e)                       #remove the selected edge (1st)
      
    #now, we have to recalculate the probabilities of edges based on the new edge added to the network
    if tecnica==1:
        pass
    elif tecnica==2:
        aristocratic(e, lista_prob_archi) 
    elif tecnica==3:
        social(e, lista_prob_archi, graph, g_complete)
    
    return e

def social(node, lista_prob_archi, g, g_complete=None):
    
    list_increase_prob={}                                        #contains edges that will be shifted to other probability sets
    
    u=node[0]
    v=node[1]
    
    for j in range(0,2):
        soc_edges=set()
        soc_edges.update([(e,node[j]) for e in g.neighbors(node[abs(j-1)])])
        soc_edges.update([(node[j],e) for e in g.neighbors(node[abs(j-1)])])

        soc_edges=set(filter(lambda x: not g.has_edge(x[0],x[1]), soc_edges))
        
        if g_complete != None:        
            soc_edges=set(filter(lambda x: g_complete.has_edge(x[0],x[1]), soc_edges))
         
        for k in lista_prob_archi.keys():
            if soc_edges == set():
                break
            #subset = set(filter(lambda x: x in soc_edges, lista_prob_archi[k]))
            subset = soc_edges & lista_prob_archi[k]
            list_increase_prob.setdefault(k+1,set())
            list_increase_prob[k+1].update(subset)
            lista_prob_archi[k] = lista_prob_archi[k]-subset
            soc_edges = soc_edges-subset
        
    g.add_edge(u,v)
    shift_set(list_increase_prob,lista_prob_archi)
    
    #if soc_count>0:
    #    print ta,soc_count 
        
def aristocratic(node, lista_prob_archi):
    
    #lista_prob_archi={1:[(1,2),(2,3)], 2:[(1,9)]...} contiene gruppi di archi, ognuno con una probabilita' di esser scelti
      
    #list_increase_prob ha la stessa struttura di lista_prob_archi, e' una struttura dati di supporto e viene utilizzata per salvare gli archi 
    #che devono essere spostati in altri gruppi (con probabilita' diversa). L'indice che identifica il gruppo di archi e' quello in cui 
    #gli archi verranno messi nella struttura lista_prob_archi 
    
    list_increase_prob={}                                        #contains edges that will be shifted to other probability sets
    u=node[0]
    v=node[1]
    
    #having edge (u,v), found all edges that have source or target equal to 'u' or 'v'. Remove them from the belongin set of "lista_prob_archi" and
    #add to the set that has higher probability
    
    for j in [u,v]:
        
        for k in lista_prob_archi.keys():
            
            subset = set(filter(lambda x:x[0]==j or x[1]==j,lista_prob_archi[k]))
            
            list_increase_prob.setdefault(k+1,set())
            list_increase_prob[k+1].update(subset)
            lista_prob_archi[k] = lista_prob_archi[k]-subset           
    
    #posiziona gli archi negli insiemi di lista_prob_archi            
    shift_set(list_increase_prob,lista_prob_archi)
    
def shift_set(list_increase_prob, lista_prob_archi):
    #list_increase_prob contains all edges (with probabilities) that must be inserted in the master list.
    for k in list_increase_prob.keys():
        lista_prob_archi.setdefault(k,set())
        lista_prob_archi[k].update(list_increase_prob[k])
        a=list(lista_prob_archi[k])
        shuffle(a)
        lista_prob_archi[k]=set(a)
        
    #remove empty lists
    toDelete = [k for k in lista_prob_archi.keys() if lista_prob_archi[k]==set()]
    
    for k in toDelete:
        del lista_prob_archi[k]
    

def get_rule_name(tecnica):
    if tecnica==1:
        return "rnd"
    elif tecnica==2:
        return "ari"
    elif tecnica==3:
        return "soc"
 
def init_aristocratic(g,nnodi):
    
    tmp = g.degree()
    
    GO=[0]    #dato che le liste partono da indice 0, e i nodi partono da indice 1, inserisco in testa alla lista uno zero 
    
    for d in sorted(tmp.keys()):    #cicla sui nodi
        GO.append(tmp[d])
    
    GO_incr = [0]*(nnodi+1)
    
    d_max   = max(GO)
    
    #descrittori is a dictionary whose keys are degrees of the graph. Every element will be initialized as empty set.
    descrittori=dict(tuple(zip(range(1,d_max+1),[set() for i in range(1,d_max+1)])))   #init descrittori
    
    node_list=range(1,nnodi+1)
    for i in tmp.keys():
        if tmp[i]==0:
            print node_list.remove(i)
    #node_list will contains nodes ids that have degree greater than 1
    shuffle(node_list)
    
    #insert shuffled nodes into the first descriptor
    descrittori[1]=set(node_list)
    
    return descrittori, GO, GO_incr
   
def aristocratic_original(index,descrittori,GO_incr,GO,g ):
    
    #GO e GO_incr hanno dim nnodi+1
    
    #TODO: la riga successiva non e' molto ottimizzata. Sappiamo che il sampling su sets non e' performante. 
    #Per questo si dovrebbe utilizzare il shuffling del set (a partire da una lista) utilizzando la funzione pop per estrarre un elemento
    source_node = random.sample(descrittori[index],1)[0]
    
    try:
        target_node = random.sample(g.neighbors(source_node),1)[0]
    except:
        print g.neighbors(source_node)
        print source_node
        print index
        
        sys.exit()
    GO_incr[source_node]+=1
    GO_incr[target_node]+=1
    g.remove_edge(source_node,target_node)
    
    #elimina il source ed il target node dalla lista in cui si trova
    descrittori[index].remove(source_node)
    descrittori[GO_incr[target_node]].remove(target_node)
    
    #inserisci il taget node nel descrittore corretto
    if GO[source_node]!=GO_incr[source_node]:
        descrittori[index+1].update([source_node])
        
    if GO[target_node]!=GO_incr[target_node]:
        descrittori[GO_incr[target_node]+1].update([target_node])

    return (source_node, target_node)

def preferential(index,descrittori,GO_incr,g,nnodi):
    
    #GO e GO_incr hanno dim nnodi+1
    
    #TODO: la riga successiva non e' molto ottimizzata. Sappiamo che il sampling su sets non e' performante. 
    #Per questo si dovrebbe utilizzare il shuffling del set (a partire da una lista) utilizzando la funzione pop per estrarre un elemento
    
    
    try:
    	source_node = random.sample(descrittori[index],1)[0]
        target_node = random.sample(g.neighbors(source_node),1)[0]
    except:
    	print "error in preferential function"
        print g.neighbors(source_node)
        print source_node
        print index
        
        sys.exit()
    GO_incr[source_node]+=1
    GO_incr[target_node]+=1
    g.remove_edge(source_node,target_node)
    
    #elimina il source ed il target node dalla lista in cui si trova
    descrittori[index].remove(source_node)
    
    #inserisci il taget node nel descrittore corretto
    if nnodi!=GO_incr[source_node]:
        descrittori[index+1].update([source_node])

    return (source_node, target_node)
